/* Поиск подстрок (Алгоритм Рабина-Карпа) */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define WRONG_INPUT \
{ \
	printf("wrong input, usage: ./rabin_karp file.txt\n"); \
	exit(0); \
}

int main(int argc, char *argv[])
{
	FILE* file = NULL;	
	unsigned int str_hash = 0, text_hash = 0;
	unsigned int symbol = 0;
	char *text = NULL;
	char s[1000] = {0};
	int i = 0, n = 0, pos = 0, k = 0;
	if (argc != 2) WRONG_INPUT;
	//argv[1] - file name
	file = fopen(argv[1], "r");
	if (!file) WRONG_INPUT;	
	gets(s);
	n = strlen(s);	
	//string hash
	for (i = 0; i < n; i++)
		str_hash += s[i];
	//get text
	text = (char*) calloc(n, sizeof(char));
	for (i = 0; i < n; i++) 
		if (fscanf(file, "%c", &text[i]) == EOF) WRONG_INPUT;
	//text hash
	for (i = 0; i < n; i++)
		text_hash += text[i];
	symbol = 0;
	do 
	{
		if (str_hash == text_hash)
		{
			int good = 1;
			for (i = 0; i < n; i++)
				if (s[i] != text[(i+k) % n]) 
				{
					good = 0;
					break;
				}
			if (good) printf("%d\n", symbol);
		}
		text_hash -= text[k];
		text[k] = fgetc(file);
		text_hash += text[k];
		k = (k+1) % n;
		symbol++;
	} 
	while (!feof(file)); 
	fclose(file);
	return 0;
}
